package algorithm.math;

/**
 * leetcode : https://leetcode.com/problems/multiply-strings/description/
 * Difficulty : Medium
 *
 * 大数相乘，返回字符串
 *
 * 数字不会以0开头，除非本身就是0
 * 不允许用内建的大数处理方法
 * 不允许直接将输入转为integer来处理
 *
 * 参考：
 * https://leetcode.com/problems/multiply-strings/discuss/17608/AC-solution-in-Java-with-explanation
 *
 * @Author Antony
 * @Since 2018/7/25 19:37
 */
public class MultiplyStrings {

    public static void main(String[] args) {
        String a = "234";
        String b = "567";
        System.out.println(multiply_example(a,b));
        System.out.println(multiply(a,b));
    }


    /**
     * beats 93.55% - 16ms
     */
    public static String multiply(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        int[] product = new int[n1 + n2];
        for(int i=n1-1; i>=0; i--){
            for(int j=n2-1; j>=0; j--){
                int p1 = num1.charAt(i) - '0';
                int p2 = num2.charAt(j) - '0';
                product[i+j+1] += p1 * p2;
            }
        }

        int carry = 0;
        for(int i=product.length - 1; i>=0; i--){
            int tmp = (product[i] + carry) % 10;
            carry = (product[i] + carry ) / 10;
            product[i] = tmp;
        }
        StringBuilder bu = new StringBuilder();
        for(int num : product) bu.append(num);
        while(bu.length() != 0 && bu.charAt(0)=='0') bu.deleteCharAt(0);
        return bu.length()==0 ? "0" : bu.toString();
    }


    public static String multiply_example(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        int[] products = new int[n1 + n2];
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int d1 = num1.charAt(i) - '0';
                int d2 = num2.charAt(j) - '0';
                products[i + j + 1] += d1 * d2;
            }
        }
        int carry = 0;
        for (int i = products.length - 1; i >= 0; i--) {
            int tmp = (products[i] + carry) % 10;
            carry = (products[i] + carry) / 10;
            products[i] = tmp;
        }
        StringBuilder sb = new StringBuilder();
        for (int num : products) sb.append(num);
        while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}
